

import java.util.*;
public class SmartStrategy implements Strategy {
private	ArrayDeque<Integer> queueX;
private	ArrayDeque<Integer> queueY;
private	int numerator[][];
private int width;
private int height;
	public boolean CurrentsStep(int xMonster,int yMonster,int xPacman,int yPacman,Thing map[][])
	{
		boolean check = (xMonster == xPacman && yMonster == yPacman);
		if(check) return true;
		if((yMonster>0) && (map[xMonster][yMonster-1].getClass() != Wall.class) && (numerator[xMonster][yMonster-1] == -1))
		{
			queueX.add(xMonster); 
			queueY.add(yMonster-1);
			numerator[xMonster][yMonster-1]=numerator[xMonster][yMonster]+1; 
			check = (xMonster == xPacman && yMonster-1 == yPacman);
		}
		if(check) return true;
		if((yMonster<height-1) && (map[xMonster][yMonster+1].getClass() != Wall.class) && (numerator[xMonster][yMonster+1] == -1))
		{
			queueX.add(xMonster); 
			queueY.add(yMonster+1);
			numerator[xMonster][yMonster+1] = numerator[xMonster][yMonster]+1;
			check = (xMonster == xPacman && yMonster+1 == yPacman);
		}
		if(check) return true;
		if((xMonster>0) && map[xMonster-1][yMonster].getClass() != Wall.class && numerator[xMonster-1][yMonster] == -1)
		{
			queueX.add(xMonster-1);
			queueY.add(yMonster);
			numerator[xMonster-1][yMonster ] = numerator[xMonster][yMonster]+1;
			check = (xMonster-1 == xPacman && yMonster == yPacman);
		}
		if(check) return true;
		if((xMonster<width-1) &&  map[xMonster+1][yMonster].getClass() != Wall.class && numerator[xMonster+1][yMonster] == -1)
		{
			queueX.add(xMonster+1);
			queueY.add(yMonster);
			numerator[xMonster+1][yMonster] = numerator[xMonster][yMonster]+1;
			check = (xMonster+1 == xPacman && yMonster == yPacman);
		}
		return check;
		
	}

	public int SelectDirection(Thing map[][], int xMonster, int yMonster, int xPacman, int yPacman)
	{
		queueX = new ArrayDeque<Integer>(1000);
		queueY = new ArrayDeque<Integer>(1000); 
		queueX.add(xMonster);
		queueY.add(yMonster); 
		width = map.length;
		height = map[1].length; 
		numerator = new int[width][height];
		for (int i = 0;i<width;i++)
		{
			for (int j = 0;j<height;j++)
			{
				numerator[i][j] = -1;
			}
		}
		boolean flag=false;
		numerator[xMonster][yMonster]=0; 
		while(!queueX.isEmpty()) 
			{
			flag=CurrentsStep(queueX.poll(),queueY.poll(),xPacman,yPacman,map);
			if(flag) break;
			}
		if(!flag) System.err.println("Monster is Blocked");
		int i = xPacman;
		int j = yPacman;
		
		while (numerator[i][j]!=1) 
		{
			if ((j>0) && numerator[i][j] == numerator[i][j-1]+1)
				{
				j--;
				continue;
				}
			if ((j<height-1) && numerator[i][j] == numerator[i][j+1]+1)
				{
				j++;
				continue;
				}
			if ((i>0) && numerator[i][j] == numerator[i-1][j]+1)
				{
				i--;
				continue;
				}
			if ((i<width-1) && numerator[i][j] == numerator[i+1][j]+1)
				{
				i++;
				continue;
				}
		} 
		if ((j<height-1) && numerator[i][j+1] == 0)
			{
			return 0;
			}
		if ((i>0) && numerator[i-1][j] == 0) 
			{
			return 1; 
			}
		if ((j>0) && numerator[i][j-1] == 0) 
			{
			return 2;
			}
		if ((i<width-1) && numerator[i+1][j] == 0)
			{
			return 3;
			}
		return -1;
	}
	
	
}

